package _2022.hot100._198_打家劫舍;

/**
 * @author： YHSimon
 * @date： 2022-05-09 15:18
 */
public class Solution {
    // 优化 0ms
    public int rob2(int[] nums){
        int ans=0;
        int[] dp=new int[nums.length];
        int preMax=nums[0];
        for(int i=0;i<nums.length;i++){
            if(i<2){
                dp[i]=nums[i];
                ans=Math.max(ans, dp[i]);
                continue;
            }
            preMax=Math.max(preMax, dp[i-2]);
            dp[i]=preMax+nums[i];
            ans=Math.max(ans, dp[i]);
        }
        return ans;
    }

    // 1ms
    public int rob(int[] nums){
        int ans=0;
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        for(int i=0;i<nums.length;i++){
            int tmp=nums[i];
            int preMax=0;
            if(i-2>=0){
                for(int j=0;j<=i-2;j++){
                    preMax=Math.max(preMax, dp[j]);
                }
            }
            dp[i]=preMax+tmp;
            ans=Math.max(ans, dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rob2(new int[]{2,1,1,2}));
    }
}
